/**
 * LRU: Least Recently Used 最近使用
 * 如果内存优先，只缓存最近使用的，删除“沉水”数据
 * 核心API两个：get set
 * 分析：
 * 用哈希表存储数据，这样get set才够快O(1)
 * 必须是有序的，常用数据放在前面，“沉水”数据放在后面
 * 哈希表 + 有序，就是Map——其他都不行
 */ 
class LRUCache {
  private length: number
  private data: Map<any, any> = new Map()

  constructor(length: number) {
    if (length < 1) throw new Error('invalid length')
    this.length = length
  }
  set(key: any, value: any) {
    const data = this.data
    if(data.has(key)) {
      data.delete(key)
    }
    data.set(key, value)
    if(data.size > this.length) {
      // 如果超出了容量，则删除 Map 最老的元素
      const delKey = data.keys().next().value
      data.delete(delKey)
    }
  }
  get(key: any): any {
    const data = this.data
    if(!data.has(key)) return null
    const value = data.get(key)
    data.delete(key)
    data.set(key, value)
    return value 
  }
}